package stool.sort;

import static stool.sort.resource.ResourceClass.*;

/**
 * @author Felix
 * @Description 插入排序
 * @Date 2022-07-07
 */
public class InsertionSort {

    public static void main(String[] args) {
        int[] arr = findIntArr();
//        insertionSort(arr);
        insertionSort(arr, 1);
        print(arr);
    }

    /**
     * 检查第i个数字，如果在它左边的数字比他大，进行交换，这个动作一直继续下去，知道这个数字的左边的数字比它小就停止
     * @param arr 排序数组
     */
    public static void insertionSort(int[] arr) {

        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    public static void insertionSort(int[] arr, int len) {

        int tempVar;
        for (int i = 0; i < len; i++) {
            for (int j = i + len; j < arr.length; j += len) {
                // k是有序序列最后一个数
                int k = j - len;
                // 要插入的元素
                tempVar = arr[j];
                while (k >= 0 && tempVar < arr[k]) {
                    arr[k + len] = arr[k];
                    // 向后移动len位
                    k -= len;
                }
                arr[k + len] = tempVar;
            }
        }
    }
}
